/**
 * Universidad Del Valle De Guatemala.
 * Algoritmos y Estructuras de Datos.
 * Sección 20.
 * Miguel Enrique Zea Arenales.
 * Carné 09238.
 * Hoja de Trabajo 8.
 * 08/11/2012
 */
package shortestpath;

import java.util.ArrayList;

/**
 * Clase empleada para realizar los algoritmos de búsqueda de rutas y del centro
 * del grafo.
 */
public class PathSearcher {
    
    /**
     * Pre: debe existir un grafo que posea una matriz de adyacencia asociada.
     * Post: se emplea el algoritmo de Floyd para obtener tanto los caminos más
     * cortos para todos los nodos, como para obtener la ruta mínima de un nodo
     * origen a un nodo destino.
     */
    public static ArrayList<Integer> FloydPathSearch(int[][] adjMatrix, int[][] pathMatrix, int origin, int destination) {
        int n, i, j, k, e; 
        n = adjMatrix.length;
        ArrayList<Integer> path = new ArrayList<>();
        
        for(k = 0; k < n; k++) {
            for(i = 0; i < n; i++) {
                for(j = 0; j < n; j++) {
                    if((adjMatrix[i][k] + adjMatrix[k][j]) < adjMatrix[i][j]) {
                        adjMatrix[i][j] = adjMatrix[i][k] + adjMatrix[k][j];
                        pathMatrix[i][j] = pathMatrix[k][j];
                    }
                }
            }
        }
        
        path.add(origin);
        e = destination;
        while(pathMatrix[origin][destination] != origin) {
            path.add(pathMatrix[origin][destination]);
            destination = pathMatrix[origin][destination];
    	}
        path.add(e);
        path.add(adjMatrix[origin][e]);
        
        return path;
    }
    
    /**
     * Pre: debe haberse efectuado previamente el algoritmo de Floyd sobre un
     * grafo.
     * Post: se obtiene el centro del grafo mediante los resultados del algoritmo
     * de Floyd.
     */
    public static int GraphCenter(int[][] adjMatrix) {
        ArrayList<Integer> Eccentricities = new ArrayList<>();
        int n, i, j, k, maxWeight, minEcc;
        n = adjMatrix.length;
        
        for(j = 0; j < n; j++) {
            maxWeight = -999999;
            for(i = 0; i < n; i++) {
                if(adjMatrix[i][j] > maxWeight) {
                    maxWeight = adjMatrix[i][j];
                }
            }
            Eccentricities.add(maxWeight);
        }
        
        minEcc = 999999;
        for(k = 0; k < Eccentricities.size(); k++) {
            if(Eccentricities.get(k) < minEcc) {
                minEcc = Eccentricities.get(k);
            }
        }
        
        return Eccentricities.indexOf(minEcc);
    }
    
}
